fn mul_mod(x: u64, y: u64, m: u64) -> u64 {
    (x as u128 * y as u128 % m as u128) as u64
}

fn pow_mod(mut x: u64, mut y: u64, m: u64) -> u64 {
    let mut ret = 1;
    while y > 0 {
        if y & 1 == 1 {
            ret = mul_mod(ret, x, m);
        }
        x = mul_mod(x, x, m);
        y >>= 1;
    }
    ret
}

/// 判断 x 是否为素数
fn is_prime(x: u64) -> bool {
    // 对小质数和常见合数的快速检查路径
    if x <= 5 {
        return x > 1 && x != 4;
    }
    if x % 2 == 0 || x % 3 == 0 || x % 5 == 0 {
        return false;
    }

    // Miller-Rabin 素性测试
    let k = (x - 1).trailing_zeros();
    let t = (x - 1) >> k;
    let mr_test = |x: u64, probe: u64| -> bool {
        let mut cur = pow_mod(probe, t, x);
        for _ in 0..k {
            let nxt = mul_mod(cur, cur, x);
            if nxt == 1 && cur != 1 && cur != x - 1 {
                return false;
            }
            cur = nxt;
        }
        cur == 1
    };

    // https://miller-rabin.appspot.com/
    match x {
        x if x < 341531 => mr_test(x, 9345883071009581737),
        x if x < 21652684502221 => [2, 1215, 34862, 574237825]
            .into_iter()
            .all(|probe| mr_test(x, probe)),
        _ => panic!("unsupported range"),
    }
}

pub fn min_edge_prime_num(percent: u32) -> String {
    let mut cnt = 0;
    let mut n = 3;
    loop {
        for x in [n * n - (n - 1) * 3, n * n - (n - 1) * 2, n * n - (n - 1)] {
            if is_prime(x) {
                cnt += 1;
            }
        }
        if cnt * 100 < percent as u64 * (n * 2 - 1) {
            return format!("{n},{cnt}");
        }
        n += 2;
    }
}
